前言

還記得上篇介紹在這電腦世代隨處可見的演算法嗎？
每個問題都有很多解法，但在程式設計的世界裡，你要怎麼知道你的解法是最佳解呢？
身為一個優良的工程師，就必須學會分析演算法的 複雜度(Complexity Analysis)！
這樣才能知道自己寫出來的演算法是不是

演算法的複雜度有以下兩種

1. 時間複雜度 (Time Complexity)： 執行演算法時須花費的時間。

• 須算出每一段的功能的執行次數
• 將所有執行次數加總起來後
• 求出此演算法的時間複雜度 ── Big-O。

2. 空間複雜度 (Space Complexity)： 執行演算法時須花費的記憶體空間。

上述是什麼意思呢？待我娓娓道來。

時間複雜度 (Time Complexity)

想知道演算法是否好壞，不能單單用執行秒數來做衡量。為什麼呢？
要是我用 NASA 的超級電腦和你現在用的電腦比較執行速度，一定是有失公允。
即使是同一個演算法，執行速度會因每個人的環境、電腦硬體、設備等而不同。而且現在設備越來越便宜，大家的設備普遍都有一定的等級。

這也就說明時間複雜度比空間複雜度來的重要！
要先了解時間複雜度，就得先學會計算演算法的執行次數。

基本粗估算法

C#

x = x + 1;

執行次數：1 次

for (int i = 0; i < n-1; i++)
{
    x = x + 1;
}

執行次數：n 次

for (int i = 0; i < n-1; i++)
{
    for (int j = 0; j < n-1; j++)
    {
        x = x + 1;
    }
}

執行次數：n^2 次

陣列加總

C#

int Sum(int[] numbers)
{
    int total = 0;
    for (int i = 0; i < numbers.Length; i++)
    {
        total += numbers[i];
    }
    return total;
}

假設輸入的陣列 int[] numbers 的個數為 n，則

line 3 -> 1 次
line 4 -> ３*(n+1) 次
line 5 -> n 次
line 8 -> 1 次

執行次數：4n+5 次

印出 n*n 的正方型

C#

void PrintSquare(int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            Console.Write("*");
        }
        Console.WriteLine();
    }
}

line 3 : -> 3*(n+1) 次
line 5 : -> 3*(n+1) 次
line 7 : -> n^2^ 次
line 8 : -> n 次

執行次數：n^2+7n+6 次

Big-O

Big-O 用來表示演算法的複雜度的執行效率。
Big-O 只顯示演算法執行次數部分的最大指數、最高次方數或是常數1，並以大 O 符號表示，例如

1. 陣列加總的執行次數為4n+5，Big-O 則是 O(n)
2. 印出 n*n 的正方型的執行次數為n^2+7n+6，Big-O 則是 O(n^2)

為什麼會用這樣的方式表示呢？
因為當 n 非常大時，影響最大的絕對是執行次數裡的最大指數、最高次方等，所以其它常數、次方數就會被省略。

Big-O 的效率分析

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n^2^)
6. O(n^3^)
7. O(2n)
8. O(n!)

假設 n 為無限大 時，1 < log n < n < n log n < n^2 < n^3 < 2^n < n!

如上圖所示，可以知道 Big-O 複雜度越高，隨著數據規模增長，效率就會越來越差。
因此 n 越大時，寫好演算法就越重要，尤其是那種一秒鐘幾十萬人次上下的系統。

空間複雜度 (Space Complexity)

空間複雜度就跟前言所說的一樣，是計算演算法執行時所花費的記憶體空間成本。
其計算方式與時間複雜度相似，也使用 Big-O 來表示其複雜度。

基本算法

C#

int Sum(int n)
{
    int result = 0;
    for (int i = 1; i <= n; i++)
    {
        result += i;
    }
    return result;
}

這段演算法不論 n 的大小，都會建立一樣個數的變數，也就是說每次執行都是耗費一樣的記憶體空間。
故空間複雜度為 O(1)。

int[] CreateArray(int n)
{
    int[] result = new int[n];
    for (int i = 0; i < n; i++)
    {
        result[i] = i;
    }
    return result;
}

這段演算法因為會根據使用者輸入的 n 來決定int array大小及記憶體空間。
故空間複雜度為 O(n)。

以上就是我對演算法的複雜度及Big-O的介紹啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉